// 给一个字符串s，找到s中最长的回文子串

// 思路，动态规划
// 子串是要在字符串中连续的
// 主要是定义状态转移方程，以及更新最长回文子串的位置和长度，初始化一个n * n大小的布尔类型数组dp[][], dp[i][j]表示字符串s上从位置i到j的子串s[i...j]
// 是否是一个回文串
// 当子串只有1位或者2位，如果s[i] === s[j],该子串为回文子串， dp[i][j] = s[i] === s[j]
// 如果子串大于2位，则如果s[i + 1...j-1]是回文串，且s[i] === s[j], 则s[i...j]也是回文串
// dp[i][j] = s[i] === s[j] && dp[i + 1][j - 1]
// 当判断完s[i:j]是否为回文串时，判断并更新最长回文子串的起始位置和最大长度

function longestPalindrome(s) {
    if (s.length <= 1) {
        return s
    }
    let len = s.length
    let dp = new Array(len).fill(0).map(_ => new Array(len).fill(0))
    let maxLen = 1
    let maxStart = 0
    for (let j = 0; j < len; j++) {
        for (let i = 0; i <= j; i++) {
            if (s[i] === s[j]) {
                if (j - i <= 2) {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[i+1][j-1]
                }
            }            
            if (dp[i][j] && (j - i + 1) > maxLen) {
                maxLen = j - i + 1
                maxStart = i
            }
        }
    }
    return s.substring(maxStart, maxStart + maxLen)
}

let s = "babad"
console.log(longestPalindrome(s));